'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-26 10:23:27
'''
'''
329. 矩阵中的最长递增路径
给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。
示例 2:

输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

tips:dfs,遍历过程中用一个数组记录改点多能到的最长递增矩阵。然后遍历nums即可。最后从保存矩阵中找寻最大值即可。
不难，有了思路之后。思路最重要呀。
'''
from typing import List
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        from sys import maxsize
        store = [[-maxsize]*len(matrix[0]) for _ in matrix]
        dires = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        def recurse(store, i, j):
            if store[i][j] != -maxsize:
                return store[i][j]
            test=False
            for dire in dires:
                dx = dire[0]
                dy = dire[1]
                new_x, new_y = i+dx, j+dy
                if 0<=new_x<len(matrix) and 0<=new_y<len(matrix[0]) and matrix[new_x][new_y]>matrix[i][j]:
                    test = True
                    store[i][j] = max(store[i][j], 1+recurse(store, new_x, new_y))
            if not test:
                store[i][j] = 1
            return store[i][j]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                recurse(store, i, j)
        # print(store)
        re = -maxsize
        for i in store:
            for j in i:
                re = max(re, j)
        return re if re != -maxsize else 0
if __name__ == "__main__":
    solution = Solution()
    nums = [[3,4,5],[3,2,6],[2,2,1]]
    print(solution.longestIncreasingPath(nums))